package myGraph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

class Edge                //边数组元素类
{
    int u;                //边的起始顶点
    int v;                //边的终止顶点
    int w;                //边的权值

    public Edge(int u, int v, int w)    //构造方法
    {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

public class MatGraph    //图邻接矩阵类
{
    static final int MAXV = 100;        //表示最多顶点个数
    static final int MAXE = 100;        //表示最多边个数
    final int INF = 0x3f3f3f3f;        //表示∞
    int[][] edges;            //邻接矩阵数组，元素为int类型
    static int[] visited;
    int n, e;                //顶点数，边数
    String[] vexs;            //存放顶点信息

    public MatGraph()        //构造方法
    {
        edges = new int[MAXV][MAXV];
        vexs = new String[MAXV];
    }

    //图的基本运算算法
    public void createMatGraph(int[][] a, int n, int e) {
        this.n = n;
        this.e = e;        //置顶点数和边数
        for (int i = 0; i < n; i++) {
            edges[i] = new int[n];
            for (int j = 0; j < n; j++)
                edges[i][j] = a[i][j];
        }
    }

    public void dispMatGraph()        //输出图
    {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                if (edges[i][j] == INF) System.out.printf("%4s", "∞");
                else System.out.printf("%5d", edges[i][j]);
            System.out.println();
        }
    }

    public static int degree1(MatGraph g, int v)
    //无向图邻接矩阵中求顶点v的度
    {
        int d = 0;
        for (int j = 0; j < g.n; j++)    //统计第v行的非0非∞元素个数
            if (g.edges[v][j] != 0 && g.edges[v][j] != g.INF) d++;
        return d;
    }

    public static int[] degree2(MatGraph g, int v)
    //有向图邻接矩阵中求顶点v的出度和入度
    {
        int[] ans = new int[2];
        ans[0] = 0;            //累计出度
        for (int j = 0; j < g.n; j++)    //统计第v行的非0非∞元素个数为出度
            if (g.edges[v][j] != 0 && g.edges[v][j] != g.INF) ans[0]++;
        ans[1] = 0;            //累计入度
        for (int i = 0; i < g.n; i++)    //统计第v列的非0非∞元素个数为入度
            if (g.edges[i][v] != 0 && g.edges[i][v] != g.INF) ans[1]++;
        ;
        return ans;            //返回出度和入度
    }

    public static void DFS(MatGraph g, int v) { //邻接矩阵深度遍历
        System.out.print(v + " ");         //访问顶点v
        visited[v] = 1;             //置已访问标记
        for (int w = 0; w < g.n; w++) {
            if (g.edges[v][w] != 0 && g.edges[v][w] != g.INF) {
                if (visited[w] == 0)         //存在边<v,w>并且w没有访问过
                    DFS(g, w);             //若w顶点未访问,递归访问它
            }
        }
    }

    public static void BFS(MatGraph g, int v) {//邻接矩阵广度遍历
        Queue<Integer> qu = new LinkedList<Integer>();    //定义一个队列
        System.out.print(v + " ");            //访问顶点v
        visited[v] = 1;                //置已访问标记
        qu.offer(v);                //v进队
        while (!qu.isEmpty())            //队列不空循环
        {
            v = qu.poll();                //出队顶点v
            for (int w = 0; w < g.n; w++) {
                if (g.edges[v][w] != 0 && g.edges[v][w] != g.INF) {
                    if (visited[w] == 0)        //存在边<v,w>并且w未访问
                    {
                        System.out.print(w + " ");    //访问顶点w
                        visited[w] = 1;            //置已访问标记
                        qu.offer(w);            //w进队
                    }
                }
            }
        }
    }

    public static void prim(MatGraph g, int v)    //prim算法
    {
        int[] lowcost = new int[MAXV];    //建立数组lowcost
        int[] closest = new int[MAXV];    //建立数组closest
        int min, k;
        for (int i = 0; i < g.n; i++) {        //给lowcost[]和closest[]置初值
            lowcost[i] = g.edges[v][i];
            closest[i] = v;
        }
        for (int i = 1; i < g.n; i++) {       //找出最小生成树的n-1条边
            min = g.INF;
            k = -1;
            for (int j = 0; j < g.n; j++)        //在(V-U)中找出离U最近的顶点k
                if (lowcost[j] != 0 && lowcost[j] < min) {
                    min = lowcost[j];
                    k = j;            //k记录最小顶点的编号
                }
            System.out.print("(" + closest[k] + "," + k + "):" + min + "  "); //输出边
            lowcost[k] = 0;            //将顶点k移到U中
            for (int j = 0; j < g.n; j++)        //修改数组lowcost和closest
                if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j]) {
                    lowcost[j] = g.edges[k][j];
                    closest[j] = k;
                }
        }
    }

    public static void kruskal(MatGraph g) //Kruskal算法
    {
        int[] vset = new int[MAXV];            //建立数组vset
        Edge[] E = new Edge[MAXE];            //建立存放所有边的数组E
        int k = 0;                    //E数组下标从0开始
        for (int i = 0; i < g.n; i++)            //由g产生的边集数组E
            for (int j = 0; j < i; j++)            //仅考虑下三角部分的边
                if (g.edges[i][j] != 0 && g.edges[i][j] != g.INF) {
                    E[k] = new Edge(i, j, g.edges[i][j]);
                    k++;
                }
        Arrays.sort(E, 0, k, new Comparator<Edge>()    //E数组按w递增排序
        {
            public int compare(Edge o1, Edge o2)    //返回值>0时进行交换
            {
                return o1.w - o2.w;
            }
        });
        for (int i = 0; i < g.n; i++)
            vset[i] = i;                //初始化辅助数组

        int cnt = 1;                //cnt表示当前构造第几条边,初值为1
        int j = 0;                //取E中边的下标,初值为0
        while (cnt < g.n)            //生成的边数小于n时循环
        {
            int u1 = E[j].u;
            int v1 = E[j].v;    //取一条边的头尾顶点
            int sn1 = vset[u1];
            int sn2 = vset[v1];        //分别得到两个顶点所属连通分量编号
            if (sn1 != sn2)            //两顶点属于不同连通分量添加
            {
                System.out.print("(" + u1 + "," + v1 + "):" + E[j].w + "  ");  //输出边
                cnt++;            //生成边数增1
                for (int i = 0; i < g.n; i++)    //两个连通分量统一编号
                    if (vset[i] == sn2)        //将sn2的连通分量中顶点改为sn1
                        vset[i] = sn1;
            }
            j++;                //继续取E的下一条边
        }
    }

    static int[] parent = new int[MAXV];                //并查集存储结构
    static int[] rank = new int[MAXV];                //存储结点的秩

    public static void init(int n)                    //并查集初始化
    {
        for (int i = 0; i < n; i++)                        //顶点编号为0～n-1
        {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public static int find(int x)                //并查集中查找x结点的根结点
    {
        if (x != parent[x]) parent[x] = find(parent[x]);            //路径压缩
        return parent[x];
    }

    public static void union(int x, int y)        //并查集中x和y的两个集合的合并
    {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry)                                //x和y属于同一棵树的情况
            return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;                        //rx结点作为ry的孩子
        else {
            if (rank[rx] == rank[ry])                //秩相同，合并后rx的秩增1
                rank[rx]++;
            parent[ry] = rx;                        //ry结点作为rx的孩子
        }
    }

    public static void kruskalImporve(MatGraph g)    //输出最小生成树
    {
        Edge[] E = new Edge[MAXE];                    //建立存放所有边的数组E
        int k = 0;                                    //E数组下标从0开始
        for (int i = 0; i < g.n; i++)                        //由邻接矩阵g产生的边集数组E
            for (int j = 0; j < i; j++)                    //对于无向图仅考虑下三角部分的边
                if (g.edges[i][j] != 0 && g.edges[i][j] != g.INF) {
                    E[k] = new Edge(i, j, g.edges[i][j]);
                    k++;
                }
        Arrays.sort(E, 0, k, new Comparator<Edge>()    //E数组按w递增排序
        {
            public int compare(Edge o1, Edge o2) //返回值>0时进行交换
            {
                return o1.w - o2.w;
            }
        });
        init(g.n);
        int cnt = 1;                                    //cnt表示当前构造生成树的第几条边,初值为1
        int j = 0;                                    //取E中边的下标,初值为0
        while (cnt < g.n)                                //生成的边数小于n时循环
        {
            int u1 = E[j].u;
            int v1 = E[j].v;            //取一条边的头尾顶点
            int sn1 = find(u1);
            int sn2 = find(v1);                        //分别得到两个顶点所属的集合编号
            if (sn1 != sn2)                            //两顶点属于不同的集合,加入不会构成回路
            {
                System.out.print("(" + u1 + "," + v1 + "):" + E[j].w + "  "); //输出最小生成树的边
                cnt++;                                //生成边数增1
                union(u1, v1);                        //合并
            }
            j++;                                    //继续取E的下一条边
        }
    }

    public static void dijkstra(MatGraph g, int v) { //dijkstra算法
        int[] dist = new int[MAXV];        //建立dist数组
        int[] path = new int[MAXV];        //建立path数组
        int[] S = new int[MAXV];        //建立S数组
        for (int i = 0; i < g.n; i++) {
            dist[i] = g.edges[v][i];        //最短路径长度初始化
            S[i] = 0;                //S[]置空
            if (g.edges[v][i] < g.INF)    //最短路径初始化
                path[i] = v;           //v到i有边，置路径上顶点i的前驱为v
            else               //v到i没边，置路径上顶点i的前驱为-1
                path[i] = -1;
        }
        S[v] = 1;                //源点v放入S中
        int u = -1;
        int mindis;
        for (int i = 0; i < g.n - 1; i++) {      //循环向S中添加n-1个顶点
            mindis = g.INF;            //mindis置求最小长度的初值
            for (int j = 0; j < g.n; j++)        //选取不在S中且具有最小距离的顶点u
                if (S[j] == 0 && dist[j] < mindis) {
                    u = j;
                    mindis = dist[j];
                }
            S[u] = 1;                //顶点u加入S中
            for (int j = 0; j < g.n; j++)        //修改不在s中的顶点的距离
                if (S[j] == 0)            //仅仅修改S中的顶点j
                    if (g.edges[u][j] < g.INF && dist[u] + g.edges[u][j] < dist[j]) {
                        dist[j] = dist[u] + g.edges[u][j];
                        path[j] = u;
                    }
        }
        dispAllPath(dist, path, S, v, g.n);    //输出所有最短路径及长度
    }

    private static void dispAllPath(int[] dist, int[] path, int[] S, int v, int n) {
        int[] apath = new int[MAXV];
        int d;            //path[0..d]存放一条最短路径(逆向)
        for (int i = 0; i < n; i++)        //循环输出从顶点v到i的路径
            if (S[i] == 1 && i != v) {
                System.out.printf("  从%d到%d最短路径长度: %d \t路径:", v, i, dist[i]);
                d = 0;
                apath[d] = i;            //添加路径上的终点
                int k = path[i];
                if (k == -1)                //没有路径的情况
                    System.out.println("无路径");
                else {                  //存在路径时输出该路径
                    while (k != v) {
                        d++;
                        apath[d] = k;        //顶点k加入到路径中
                        k = path[k];
                    }
                    d++;
                    apath[d] = v;            //添加路径上的起点
                    for (int j = d; j >= 0; j--)        //输出最短路径
                        System.out.print(apath[j] + " ");
                    System.out.println();
                }
            }
    }

    public static void floyd(MatGraph g)    //弗洛伊德算法
    {
        int[][] A = new int[MAXV][MAXV];    //建立A数组
        int[][] path = new int[MAXV][MAXV];    //建立path数组
        for (int i = 0; i < g.n; i++)        //给数组A和path置初值即求A-1[i][j]
            for (int j = 0; j < g.n; j++) {
                A[i][j] = g.edges[i][j];
                if (i != j && g.edges[i][j] < g.INF) path[i][j] = i;            //i和j顶点之间有边时
                else path[i][j] = -1;            //i和j顶点之间没有边时
            }
        for (int k = 0; k < g.n; k++)            //求Ak[i][j]
        {
            for (int i = 0; i < g.n; i++)
                for (int j = 0; j < g.n; j++)
                    if (A[i][j] > A[i][k] + A[k][j]) {
                        A[i][j] = A[i][k] + A[k][j];
                        path[i][j] = path[k][j];    //修改最短路径
                    }
        }
        disFloydPath(A, path, g);            //生成最短路径和长度
    }

    public static void disFloydPath(int[][] A, int[][] path, MatGraph g) {
        //输出所有的最短路径和长度
        int[] apath = new int[MAXV];
        int d;            //apath[0..d]存放一条最短路径(逆向)
        for (int i = 0; i < g.n; i++)
            for (int j = 0; j < g.n; j++) {
                if (A[i][j] != g.INF && i != j) {        //若顶点i和j之间存在路径
                    System.out.print("  顶点" + i + "到" + j +
                            "的最短路径长度:" + A[i][j] + "\t路径:");
                    int k = path[i][j];
                    d = 0;
                    apath[d] = j;            //路径上添加终点
                    while (k != -1 && k != i) {       //路径上添加中间点
                        d++;
                        apath[d] = k;        //顶点k加入到路径中
                        k = path[i][k];
                    }
                    d++;
                    apath[d] = i;            //路径上添加起点
                    for (int s = d; s >= 0; s--)        //输出最短路径
                        System.out.print(" " + apath[s]);
                    System.out.println();
                }
            }
    }


    public static void main(String[] args) {


        MatGraph g0 = new MatGraph();
        int n0 = 6, e0 = 10;
        int[][] a0 = {{0, 6, 1, 5, g0.INF, g0.INF}, {6, 0, 5, g0.INF, 3, g0.INF}, {1, 5, 0, 5, 6, 4}, {5, g0.INF, 5, 0, g0.INF, 2}, {g0.INF, 3, 6, g0.INF, 0, 6}, {g0.INF, g0.INF, 4, 2, 6, 0}};  //图7.21(a)的边数组
        g0.createMatGraph(a0, n0, e0);
        System.out.println("********Prim*******");
        System.out.println("图g");
        g0.dispMatGraph();
        System.out.print("最小生成树: ");
        prim(g0, 0);
        System.out.println("");

        MatGraph g = new MatGraph();
        int n = 6, e = 10;
        int[][] a = {{0, 6, 1, 5, g.INF, g.INF}, {6, 0, 5, g.INF, 3, g.INF}, {1, 5, 0, 5, 6, 4}, {5, g.INF, 5, 0, g.INF, 2}, {g.INF, 3, 6, g.INF, 0, 6}, {g.INF, g.INF, 4, 2, 6, 0}};  //图7.21(a)的边数组
        g.createMatGraph(a, n, e);
        System.out.println("********Kruskal*******");
        System.out.println("图g");
        g.dispMatGraph();
        System.out.print("Kruskal: ");
        kruskal(g);
        System.out.println("");
        System.out.print("改进Kruskal: ");
        kruskalImporve(g);
        System.out.println("");


        MatGraph g1 = new MatGraph();
        int n1 = 7, e1 = 12;
        int[][] a1 = {{0, 4, 6, 6, g1.INF, g1.INF, g1.INF}, {g1.INF, 0, 1, g1.INF, 7, g1.INF, g1.INF}, {g1.INF, g1.INF, 0, g1.INF, 6, 4, g1.INF}, {g1.INF, g1.INF, 2, 0, g1.INF, 5, g1.INF}, {g1.INF, g1.INF, g1.INF, g1.INF, 0, g1.INF, 6}, {g1.INF, g1.INF, g1.INF, g1.INF, 1, 0, 8}, {g1.INF, g1.INF, g1.INF, g1.INF, g1.INF, g1.INF, 0}};
        g1.createMatGraph(a1, n1, e1);
        System.out.println("********Dijkstra*******");
        System.out.println("图g");
        g1.dispMatGraph();
        System.out.println(" 最短路径");
        dijkstra(g1, 0);

        MatGraph g2 = new MatGraph();
        int n2 = 4, e2 = 8;
        int[][] a2 = {{0, 5, g2.INF, 7}, {g2.INF, 0, 4, 2}, {3, 3, 0, 2}, {g2.INF, g2.INF, 1, 0}};
        System.out.println("********Floyd*******");
        g2.createMatGraph(a2, n2, e2);
        System.out.println("图g");
        g2.dispMatGraph();
        System.out.println(" 最短路径");
        floyd(g2);
    }
}
